package array

import "fmt"

func combinationSum3(k int, n int) [][]int {
	res := [][]int{}
	var backtrack func(track []int, start int, k int, n int, sum int)

	backtrack = func(track []int, start, k, n, sum int) {
		if len(track) == k {
			if sum == n {
				fmt.Println(track)
				temp := []int{}
				copy(temp, track)
				res = append(res, temp)
			}
			return
		}

		for i := start; i <= 9; i++ {
			track = append(track, i)
			backtrack(track, i+1, k, n, sum+i)
			track = track[:len(track)-1]
		}

	}
	backtrack([]int{}, 1, k, n, 0)
	return res
}
